package com.cwj.lab3;

/**
 * 并查集
 */
public class UFset {
    int len = 0;//并查统计数据的个数
    int[] nums;//其实取名为fa更合适，祖先结点对应

    public UFset(int len) {
        this.len = len;
        nums = new int[len];
        //初始化十分重要，否则结果不正确
        for (int i = 0; i < len; i++) {
            nums[i] = i;
        }
    }

    /**
     * 路径压缩的查询
     */
    public int find(int one) {
        //路径压缩指将在查询的时候，就将对应的父节点修改为其祖先结点，以减少查询的开销
        return one == nums[one] ? one : (nums[one] = find(nums[one]));
    }
/**
 * 合并两个集
 * */
    public void union(int fir, int sec) {
        int n1 = find(fir);
        int n2 = find(sec);
        if (n1 != n2) {
            nums[n2] = n1;
        }
    }
/**
 * 是否同一个连通块
 * */
    public boolean isSame(int fir, int sec) {
        return find(fir) == find(sec);
    }
}
